Опис вхідної мови транслятора
Перша і головна відмінність одної мови програмування від іншої − це її синтаксис. Основне призначення синтаксису − надати систему позначень для обміну інформацією між програмістом і транслятором. Але при розробці деталей синтаксису частіше враховують другорядні критерії − зробити програму зручної для читання, написання і трансляції, а також, щоб програма була однозначною. Якщо зручність читання програми та її запису потрібні користувачу мови програмування, то простота трансляції та відсутність неоднозначності мають значення насамперед при процесі трансляції. Ці вимоги, взагалі кажучи, суперечливі, і знаходження компромісу є однією з центральних задач при розробці мови програмування.
Розробка нової мови починається з означення її синтаксису. Для опису синтаксису мови програмування, у свою чергу, також потрібні певні засоби. Мову, призначену для опису іншої мови, називають метамовою. Мова, що використовується для опису синтаксису мови, називається метасинтаксичною мовою. У метасинтаксичних мовах використовується спеціальна сукупність умовних знаків, яка утворює нотацію цієї мови.
Історично першою метасинтаксичною мовою, яка використовувалась на практиці для опису синтаксису мов програмування (зокрема, мови Алгол-60), є нормальні форми Бекуса, скорочене позначення БНФ ( бекусова нормальна форма або бекусово-наурова форма). Основне призначення БНФ − подання у компактному вигляді строго формальних і однозначних правил написання основних конструкцій мови програмування, яка описується.
Формальне означення синтаксису мови програмування зазвичай називається граматикою.
За допомогою БНФ описують два класи об'єктів: 1) основні символи мови програмування; 2) імена конструкцій описуваної мови або, так звані, металінгвістичні змінні.
Кожна металінгвістична формула (форма) описує правила побудови конструкцій мови і складається з двох частин. У лівій знаходиться металінгвістична змінна для позначення відповідної конструкції, за нею − металінгвістична зв'язка ::= , зміст якої − «означується як» або «є». У правій частині формули вказується один або декілька варіантів побудови конструкції, яка означується у лівій частині. Для побудови конструкції, яка означується даною формулою, потрібно вибрати деякий варіант її побудови із правої частини формули і підставити замість кожної металінгвістичної змінної деякі ланцюжки основних символів. Варіанти правої частини відокремлюються металінгвістичною зв'язкою │, яка має зміст «або».
Самі мета лінгвістичні змінні позначаються словами, що пояснюють зіст описуваної конструкції і беруться у кутові дужки < > .
Для прикладу наведемо означення десяткового числа за допомогою БНФ:
1. < десяткове ціле число > ::= < число без знаку > │
+ < число без знаку > │ - < число без знаку >
2. < число без знаку > ::= < цифра > │ < число без знаку > < цифра >
3. < цифра > ::= 0 │1 │2 │3 │4 │5 │6 │7 │8 │9
Наприклад, десяткове число +165 будується за цими формулами так:
< десяткове ціле число >
+ < число без знаку >
+ < число без знаку > < цифра >
+ < число без знаку > 5
+ < число без знаку > < цифра >5
+ < число без знаку > 65
+< цифра >65
+165
Особливістю багатьох металінгвістичних формул є наявність у них рекурсій, тобто використання для опису деяких конструкцій цих самих конструкцій. Рекурсія може бути явною і неявною. Зокрема, серед наведених вище правил у правилі 2 зустрічається явна рекурсія. Неявна рекурсія буде у тому випадку, коли при побудові конструкції на деякому кроці використовується металінгвістична змінна, яка використовується для позначення цієї самої конструкції.
Наявність рекурсій ускладнює читання і розуміння мета лінгвістичних формул, але дає змогу за допомогою скінченої кількості правил описати мову, яка може містити нескінченну кількість ланцюжків основних символів. Адже мови програмування нескінченні − на цих мовах можна написати нескінченну кількість правильних програм, і при описі їх синтаксису за допомогою БНФ завжди будуть присутні...